//最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作： 
//
// 
// Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。 
// Paste（粘贴）：粘贴 上一次 复制的字符。 
// 
//
// 给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。 
//
// 
//
// 示例 1： 
//
// 
//输入：3
//输出：3
//解释：
//最初, 只有一个字符 'A'。
//第 1 步, 使用 Copy All 操作。
//第 2 步, 使用 Paste 操作来获得 'AA'。
//第 3 步, 使用 Paste 操作来获得 'AAA'。
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 1000 
// 
// Related Topics 数学 动态规划 
// 👍 431 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;

public class TwoKeysKeyboard {
    public static void main(String[] args) {
        Solution solution = new TwoKeysKeyboard().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    class Solution {

        public int minSteps1(int n) {
            if (n == 1) {
                return 0;//最初是有一个字符存在的
            }
            return dfs(n,1,0);
        }

        /**
         * @param n 目标字符数
         * @param cur 当前有的字符数
         * @param paste 剪切板上的字符数
         * @return 在当前cur和paste的情况下，到达n的最小操作数
         */
        private int dfs(int n, int cur, int paste) {
            if (n == cur) {
                return 0;//已经满足要求了，直接返回0
            }
            if (cur>n) {
                return Integer.MAX_VALUE/2;
            }
            //当前操作选择复制：如果cur=paste的时候说明上一步已经是复制了，本次再复制就毫无价值了
            int p1 = cur!=paste ? 1 + dfs(n, cur, cur) : Integer.MAX_VALUE/2;
            //当前操作为粘贴：如果此时剪切板上没有东西，粘贴操作便毫无意义
            int p2 = paste > 0 ? 1+dfs(n, cur+paste, paste) : Integer.MAX_VALUE/2;
            return Math.min(p1, p2);
        }


        /**
         * 素数分解
         * 使用数学的解法：将1次复制K次粘贴看作一个动作的话
         * 那么一个动作之后，现有的字符个数就变成了原来的K+1倍
         * 那么可以将总数为n进行如下分解：
         * 1.原始字符数为1，进行一次复制操作，k1-1次粘贴，此时字符数为k1
         * 2.字符数为k1时进行一次复制，然后进行k2-1次粘贴，此时字符数为k1*k2
         * 3.不断分解直到n = k1 * k2 * k3 * ...kn
         * 所求的次数便是k1 + k2 + k3 + ... +kn，目的就是让n拆分成各个k相乘时其和最小
         * 又因为a*b >= a+b，所以可以将ki进行拆分
         * 只需要使用「试除法」对 n 执行分解质因数操作，累加所有的操作次数，即可得到答案
         */
        public int minSteps2(int n) {
            int ans = 0;
            for (int i = 2; i * i <= n; i++) {
                while (n % i == 0) {
                    ans += i;
                    n /= i;
                }
            }
            if (n != 1) {
                ans += n;
            }
            return ans;
        }

        /**
         * 朴素递归，自底向上的查找分解
         */
        public int minSteps(int n) {
            if (n == 1) {
                return 0;
            }
            for (int i = 2; i*i <= n ; i++) {
                if (n%i==0) {
                    return minSteps(n/i)+i;
                }
            }
            return n;
        }

        /**
         * 使用dp来做，dp保存记事本上有n个字符时的最小次数
         */
        public int minSteps4(int n) {
            int[] dp = new int[n + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[1] = 0;
            for (int i = 2; i <= n ; i++) {
                for (int j = 1; j  <= i / 2; j++) {
                    if (i % j == 0){
                        dp[i] = Math.min(dp[i], dp[j] + i / j);
                    }
                }
            }
            return dp[n];
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}


















































